翻訳と辞書 Words near each other ・ Thomson MO6 ・ Thomson Newspapers Co Ltd v Canada (AG) ・ Thomson North American Legal ・ Thomson Park (Fiji) ・ Thomson Peak ・ Thomson Plaza ・ Thomson Point ・ Thomson problem ・ Thomson railway station ・ Thomson Reuters ・ Thomson Reuters Business Classification ・ Thompson Yates and Johnston Laboratories Report ・ Thompson's Bottom ・ Thompson's Bridge ・ Thompson's Bromine and Arsenic Springs ・ Thompson's construction ・ Thompson's Corner, Maryland ・ Thompson's Harbor State Park ・ Thompson's Island ・ Thompson's Lake State Park ・ Thompson's Loss and Gain Site ・ Thompson's Mills State Heritage Site ・ Thompson's Park ・ Thompson's psychology of women ・ Thompson's snake eel ・ Thompson's Station, Tennessee ・ Thompson's War ・ Thompson, Alabama ・ Thompson, Bulgaria ・ Thompson, California Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Thompson's construction ： ウィキペディア英語版 Thompson's construction In computer science, Thompson's construction is an algorithm for transforming a regular expression into an equivalent nondeterministic finite automaton (NFA). This NFA can be used to match strings against the regular expression. Regular expression and nondeterministic finite automaton are two abstract representation of formal languages. While regular expressions are used e.g. to describe advanced search patterns in "find and replace"-like operations of text processing utilities, the NFA format is better suited for execution on a computer. Hence, this algorithm is of practical interest, since it can be considered as a compiler from regular expression to NFA. On a more theoretical point of view, this algorithm is a part of the proof that they both accept exactly the same languages, that is, the regular languages. A thus obtained automaton can be made deterministic by the powerset construction and then be minimized to get an optimal automaton corresponding to the given regular expression, but it may also be used directly. == The algorithm == The algorithm works recursively by splitting an expression into its constituent subexpressions, from which the NFA will be constructed using a set of rules. More precisely, from a regular expression , the obtained automaton with the transition function respects the following properties: * has exactly one initial state , which is not accessible from any other state. That is, for any state and any letter , $\backslash delta(q,a)$ does not contain . * has exactly one final state , which is not co-accessible from any other state. That is, for any letter , $\backslash delta(q\_f,a)=\backslash emptyset$. * Let be the number of concatenation of the regular expression and let be the number of symbols apart from parentheses — that is, , , and . Then, the number of states of is (linear in the size of ). * The number of transitions leaving any state is at most two. * Since an NFA of states and at most transitions from each state can match a string of length in time , a Thompson NFA can do pattern matching in linear time, assuming a fixed-size alphabet.〔(【引用サイトリンク】last=Xing )〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Thompson's construction」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.